#include "bits/stdc++.h"
using namespace std;
vector<vector<int>>ku;
int support;
int line=0;
string ak;

void duxie()
{

    ifstream ifs;
    ifs.open("retail.txt",ios::in);

    if (!ifs.is_open())
    {
        cout<<"fail";

    }

    while (getline(ifs,ak)) {
        stringstream ss;
        ss << ak;
        string temp;
        vector<int>temp1;
        while (ss>>temp)
            temp1.push_back(stoi(temp));
        ku.push_back(temp1);
    }
    ifs.close();

}
bool often(vector<vector<int>>&prob,int i)
{

    int n=prob[0].size();
    int flag=0;
    int num=0;
    for (int j = 0; j < ku.size(); ++j) {

        for (int k = 0; k < ku[j].size(); ++k) {
            if(prob[i][flag]==ku[j][k]) {
                flag++;
                if(flag==n)
                {   num++;
                    flag=0;
                    break;}
            } else if (prob[i][flag]<ku[j][k])
            {
                break;
            }


        }
        flag=0;
        if(num>=support)
            return true;

    }



    return  false;



}
bool synth(vector<vector<int>>&sure,int i,int j)
{
    int n=sure[i].size();
    int flag=1;

    for (int k = 0; k < n-1; ++k) {
        if(sure[i][k]!=sure[j][k]) {
            flag = 0;
            break;
        }
    }
    if (flag==1)
        return true;
    else
        return false;
}
void creatpro(vector<vector<int>>&prolib,vector<vector<int>>&sure,vector<int>jilu,int xiang)
{


    for (int i = sure.size()-jilu[xiang-1]; i <sure.size() ; ++i) {
        for (int j = i+1; j <sure.size() ; ++j) {
            if (synth(sure,i,j))
            {
                prolib.push_back(sure[i]);
                prolib[prolib.size()-1].push_back(sure[j][sure[j].size()-1]);
            } else
                break;
        }
    }

}
bool truecut(vector<vector<int>>&prolib,vector<vector<int>>&sure,vector<int>jilu,int xiang,int i)
{   int flag=0;
    int num=0;

    for (int j = sure.size()-jilu[xiang-1]; j < sure.size(); ++j) {
        for (int k = 0; k < xiang+1; ++k) {
            if(sure[j][flag]==prolib[i][k]) {
                flag++;
                if(flag==xiang)
                    break;
            }
            else  if (sure[j][flag]<prolib[i][k]) {
                flag = 0;
                break;
            }
        }

        if(flag==xiang)
            num++;
        flag=0;

        if (num==xiang+1)
            return true;
    }

    return  false;

}
void cut(vector<vector<int>>&prolib,vector<vector<int>>&sure,vector<int>jilu,int xiang)
{


    vector<vector<int>>temp;
    for (int i = 0; i <prolib.size() ; ++i) {
        if(truecut(prolib,sure,jilu,xiang,i))
            temp.push_back(prolib[i]);
    }
    prolib.clear();
    prolib=temp;
}
int main() {
    auto start_time = std::chrono::steady_clock::now();
    duxie();
    int k=2;
    int a[20000]={0};
    int num1=0;
    vector<int>jilu;

    vector<vector<int>>sure,prolib,temp;
    for (int i = 0; i < ku.size(); ++i) {
        for (int j = 0; j < ku[i].size(); ++j) {
            a[ku[i][j]]++;
        }
    }
    support=ku.size()*0.01;

    vector<int>temp1;
    for (int i = 0; i < 20000; ++i) {
        if(a[i]>=support) {
            vector<int>tempp1;
            tempp1.push_back(i);
            sure.push_back(tempp1);
            num1++;
        }
    }

    jilu.push_back(num1);
    num1=0;

    for (int i = 0; i < sure.size(); ++i) {
        for (int j = i+1; j <sure.size() ; ++j) {

            prolib.push_back({sure[i][0],sure[j][0]});

        }
    }

    for (int i = 0; i < prolib.size(); ++i) {

        if( often(prolib,i)) {
            num1++;
            sure.push_back(prolib[i]);
        }
    }

    jilu.push_back(num1);
    num1=0;
    prolib.clear();


    int xiang=2;

    while (1)
    {
        creatpro(prolib,sure,jilu,xiang);

        if(prolib.size()==0)
            break;
        cut(prolib,sure,jilu,xiang);
        if (prolib.size()==0)
            break;
        for (int i = 0; i < prolib.size(); ++i) {

            if( often(prolib,i)) {
                num1++;
                sure.push_back(prolib[i]);
            }
        }

        jilu.push_back(num1);
        num1=0;
        xiang++;
        prolib.clear();

    }
    int num=0;
    for (int i = 0; i < jilu.size(); ++i) {
        cout<<jilu[i]<<endl;
        num+=jilu[i];
    }
    cout<<endl;
    cout<<num;
    auto end_time = std::chrono::steady_clock::now();

    // 计算时间间隔
    auto elapsed_time = end_time - start_time;

    // 输出时间间隔
    std::cout << "Elapsed time: " << std::chrono::duration<double>(elapsed_time).count() << " seconds\n";
    cout<<xiang<<endl;
    return 0;
}